#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TABLE_SIZE 10 // 哈希表大小
#define EMPTY -1      // 空槽标记

// 哈希表结构（开放地址法）
struct OpenHashTable
{
    int *keys;      // 键数组
    int *values;    // 值数组
    bool *occupied; // 占用标记数组
    int size;       // 表大小
};

// 创建哈希表
struct OpenHashTable *createOpenHashTable(int size)
{
    struct OpenHashTable *table = (struct OpenHashTable *)malloc(sizeof(struct OpenHashTable));
    table->size = size;
    table->keys = (int *)malloc(size * sizeof(int));
    table->values = (int *)malloc(size * sizeof(int));
    table->occupied = (bool *)malloc(size * sizeof(bool));

    // 初始化所有槽为空
    for (int i = 0; i < size; i++)
    {
        table->keys[i] = EMPTY;
        table->occupied[i] = false;
    }

    return table;
}

// 除留余数法哈希函数（基本哈希函数）
int hashFunction(int key)
{
    return key % TABLE_SIZE;
}

// 1. 线性探测法
int linearProbing(struct OpenHashTable *table, int key, int i)
{
    return (hashFunction(key) + i) % table->size;
}

// 2. 平方探测法
int quadraticProbing(struct OpenHashTable *table, int key, int i)
{
    return (hashFunction(key) + i * i) % table->size;
}

// 3. 双重哈希法
int doubleHashing(struct OpenHashTable *table, int key, int i)
{
    int h1 = hashFunction(key);
    int h2 = 7 - (key % 7); // 第二个哈希函数
    return (h1 + i * h2) % table->size;
}

// 4. 随机探测法（伪随机序列）
int randomProbing(struct OpenHashTable *table, int key, int i)
{
    // 使用简单伪随机序列生成器
    int rand_seq[] = {3, 7, 2, 8, 1, 9, 4, 6, 5, 0}; // 预设的随机序列
    return (hashFunction(key) + rand_seq[i]) % table->size;
}

// 向哈希表插入键值对（使用指定的探测方法）
void insertWithProbing(struct OpenHashTable *table, int key, int value,
                       int (*probeFunc)(struct OpenHashTable *, int, int))
{
    for (int i = 0; i < table->size; i++)
    {
        int index = probeFunc(table, key, i);

        if (!table->occupied[index])
        {
            // 找到空槽，插入键值对
            table->keys[index] = key;
            table->values[index] = value;
            table->occupied[index] = true;

            if (i > 0)
            {
                printf("Collision resolved for key %d at attempt %d (index %d)\n", key, i, index);
            }
            return;
        }
        else if (table->keys[index] == key)
        {
            // 键已存在，更新值
            table->values[index] = value;
            return;
        }
        else if (i == 0)
        {
            printf("Collision detected for key %d at index %d\n", key, index);
        }
    }

    printf("ERROR: Hash table full, cannot insert key %d\n", key);
}

// 打印哈希表
void printOpenHashTable(struct OpenHashTable *table, const char *method)
{
    printf("\nHash Table using %s:\n", method);
    printf("Index\tKey\tValue\tOccupied\n");
    printf("----------------------------\n");

    for (int i = 0; i < table->size; i++)
    {
        printf("%d\t", i);
        if (table->occupied[i])
        {
            printf("%d\t%d\t", table->keys[i], table->values[i]);
        }
        else
        {
            printf("-\t-\t");
        }
        printf("%s\n", table->occupied[i] ? "Yes" : "No");
    }
}

int main()
{
    // 创建四个哈希表，使用不同的冲突解决方法
    struct OpenHashTable *tableLinear = createOpenHashTable(TABLE_SIZE);
    struct OpenHashTable *tableQuadratic = createOpenHashTable(TABLE_SIZE);
    struct OpenHashTable *tableDouble = createOpenHashTable(TABLE_SIZE);
    struct OpenHashTable *tableRandom = createOpenHashTable(TABLE_SIZE);

    // 测试键值对（故意制造冲突）
    int keys[] = {10, 20, 30, 15, 25, 35, 12, 22};
    int values[] = {100, 200, 300, 150, 250, 350, 120, 220};
    int n = sizeof(keys) / sizeof(keys[0]);

    printf("Demonstrating open addressing collision resolution methods:\n");

    // 插入键值对到不同的哈希表
    for (int i = 0; i < n; i++)
    {
        insertWithProbing(tableLinear, keys[i], values[i], linearProbing);
        insertWithProbing(tableQuadratic, keys[i], values[i], quadraticProbing);
        insertWithProbing(tableDouble, keys[i], values[i], doubleHashing);
        insertWithProbing(tableRandom, keys[i], values[i], randomProbing);
    }

    // 打印所有哈希表
    printOpenHashTable(tableLinear, "Linear Probing");
    printOpenHashTable(tableQuadratic, "Quadratic Probing");
    printOpenHashTable(tableDouble, "Double Hashing");
    printOpenHashTable(tableRandom, "Random Probing");

    return 0;
}